{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2eb4afa3-7350-4bfc-87d2-13ddbc7acff9",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/combination-sum-ii\n",
    "\n",
    "\n",
    "Runtime: 208 ms, faster than 8.98% of Go online submissions for Combination Sum II.\n",
    "Memory Usage: 12.1 MB, less than 5.39% of Go online submissions for Combination Sum II.\n",
    "\n",
    "\n",
    "```go\n",
    "package main\n",
    "\n",
    "import (\n",
    "\t\"fmt\"\n",
    "\t\"sort\"\n",
    ")\n",
    "\n",
    "func sum(nums []int) int {\n",
    "\tvalue := 0\n",
    "\tfor _, n := range nums {\n",
    "\t\tvalue += n\n",
    "\t}\n",
    "\treturn value\n",
    "}\n",
    "\n",
    "func remove(nums []int, target int) []int {\n",
    "\tok := false\n",
    "\tresult := make([]int, 0)\n",
    "\tfor _, n := range nums {\n",
    "\t\tif n == target {\n",
    "\t\t\tif ok == true {\n",
    "\t\t\t\tresult = append(result, n)\n",
    "\t\t\t} else {\n",
    "\t\t\t\tok = true\n",
    "\t\t\t}\n",
    "\t\t} else {\n",
    "\t\t\tresult = append(result, n)\n",
    "\t\t}\n",
    "\t}\n",
    "\treturn result\n",
    "}\n",
    "\n",
    "func Equal(a, b []int) bool {\n",
    "\tif len(a) != len(b) {\n",
    "\t\treturn false\n",
    "\t}\n",
    "\tfor i, v := range a {\n",
    "\t\tif v != b[i] {\n",
    "\t\t\treturn false\n",
    "\t\t}\n",
    "\t}\n",
    "\treturn true\n",
    "}\n",
    "\n",
    "func contains(arr [][]int, value []int) bool {\n",
    "\tfor _, v := range arr {\n",
    "\t\tif Equal(v, value) {\n",
    "\t\t\treturn true\n",
    "\t\t}\n",
    "\t}\n",
    "\n",
    "\treturn false\n",
    "}\n",
    "\n",
    "var result = make([][]int, 0)\n",
    "var the_target = 0\n",
    "\n",
    "func go_through(this_list []int, list_left []int) {\n",
    "\tif len(list_left) == 0 {\n",
    "\t\treturn\n",
    "\t} else {\n",
    "\t\tcopy_of_list_left := list_left\n",
    "\t\tfor _, num := range copy_of_list_left {\n",
    "            new_list := make([]int, 0)\n",
    "\t\t\tnew_list = append(new_list, this_list...)\n",
    "\t\t\tnew_list = append(new_list, num)\n",
    "\t\t\ts := sum(new_list)\n",
    "\t\t\tif s > the_target {\n",
    "\t\t\t\treturn\n",
    "\t\t\t} else if s == the_target {\n",
    "\t\t\t\tsort.Ints(new_list)\n",
    "\t\t\t\tresult = append(result, new_list)\n",
    "\t\t\t} else {\n",
    "\t\t\t\tl := list_left\n",
    "\t\t\t\tl = remove(l, num)\n",
    "\t\t\t\tgo_through(new_list, l)\n",
    "\t\t\t}\n",
    "\t\t}\n",
    "\t}\n",
    "}\n",
    "\n",
    "func combinationSum2(candidates []int, target int) [][]int {\n",
    "\t//8:59\n",
    "\tresult = result[:0]\n",
    "\tthe_target = target\n",
    "\n",
    "\tif sum(candidates) < target {\n",
    "\t\treturn result\n",
    "\t}\n",
    "\n",
    "\tsort.Ints(candidates)\n",
    "\tl := make([]int, 0)\n",
    "\tgo_through(l, candidates)\n",
    "\n",
    "\tnew_result := make([][]int, 0)\n",
    "\tfor _, l := range result {\n",
    "\t\thave_it := contains(new_result, l)\n",
    "\t\tif have_it {\n",
    "\t\t} else {\n",
    "\t\t\tnew_result = append(new_result, l)\n",
    "\t\t}\n",
    "\t}\n",
    "\treturn new_result\n",
    "\t//9:19\n",
    "    //debug until 9:45\n",
    "    //debug at second day morning, 7:30 to 7:50, found that for golang, if you do not use make() to create array, that array will get random value (because of memory release) after the end of its function\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c9510d25-a177-475a-88c3-a6f543fb3b22",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Go",
   "language": "go",
   "name": "gophernotes"
  },
  "language_info": {
   "codemirror_mode": "",
   "file_extension": ".go",
   "mimetype": "",
   "name": "go",
   "nbconvert_exporter": "",
   "pygments_lexer": "",
   "version": "go1.14.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}